/*
 * @lc app=leetcode.cn id=198 lang=java
 *
 * [198] 打家劫舍
 */

// @lc code=start
class Solution {
    public int rob(int[] nums) {
        //考虑当下状态：偷还是不偷，取决于前一个房间或者前两个房间是否偷窃
        //dp[i]：代表考虑i及i之前的房间时，能够偷窃到的最高金额
        //dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]) 即考虑第i个房间偷or不偷两种情况
        if(nums.length==1) return nums[0];
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];

    }
}
// @lc code=end

